import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86185
 * Date: 2023-04-21
 * Time: 19:54
 */
public class Heap {
    private int[] elem;
    private int usedSize;
    public Heap() {
        this.elem = new int[10];
    }
    //创建一个大根堆
    public void createHeap(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            elem[i] = arr[i];
            usedSize++;
        }
        //把原始数据给到了elem数组
        for(int p = (usedSize - 1 - 1) / 2; p >= 0; p--) {
            shiftDown(p, usedSize);
        }
    }

    /**
     *
     * @param p 每棵子树的根节点
     * @param e 每棵子树的结束位置
     */
    private void shiftDown(int p, int e) {
        int child = 2 * p + 1;
        //判断是不是一定有左孩子
        while(child < e) {
            //不一定有右孩子
            if(child + 1 < e && elem[child] < elem[child + 1]) {
                child += 1;
            }
            if(elem[child] > elem[p]) {
                int tmp = elem[child];
                elem[child] = elem[p];
                elem[p] = tmp;
                p = child;
                child = 2 * p + 1;
            }
        }
    }
    public void push(int val) {
        //check fill
        if(usedSize == elem.length) {
            elem = Arrays.copyOf(elem, 2 * usedSize);
        }
        //
        elem[usedSize] = val;
        usedSize++;
        shiftUp(usedSize - 1);
    }
    public void shiftUp(int child) {
        int p = (child - 1) / 2;
        while(child > 0) {
            if(elem[child] > elem[p]) {
                int tmp = elem[child];
                elem[child] = elem[p];
                elem[p] = tmp;
                child = p;
                p = (child - 1) / 2;
            } else {
                return;
            }
        }
    }

    /**
     * 删除
     */
    public void poll() {
        if(usedSize == 0) {
            System.out.println("优先级队列为空");
            return;
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize - 1];
        elem[usedSize - 1] = tmp;
        usedSize--;
        shiftDown(0, usedSize);
    }
    public int peek() throws HeapEmptyException{
        if(usedSize == 0) {
            throw new HeapEmptyException("empty");
        }
        return elem[0];
    }

}
